package org.youyee.game.pathFinding
{
	import flash.utils.Dictionary;

	/**
	 * 路径计算器
	 * @author youyee
	 * @version 2.0
	 */	
	public class PathCalculator
	{
		private var _pathMap:PathMap;
		private var _openList:Array;
		private var _openListFlag:Dictionary;
		//private var _closeList:Array;
		private var _closeListFlag:Dictionary;
		private var _startNode:PathNode;
		private var _targetNode:PathNode;
		private var _clockWise:Boolean;
		
		/**
		 * 构造函数 
		 * 
		 */		
		public function PathCalculator():void
		{
			//nothing to do...
			reset();
		}
		
		/**
		 * 重置路径计算器 
		 * 
		 */		
		public function reset():void
		{
			_pathMap = null;
			_openList = [];
			//_closeList = [];
			_openListFlag = new Dictionary();
			_closeListFlag = new Dictionary();
			_clockWise = true;
		}
		
		/**
		 * 计算路径 
		 * @param startNode 起始节点
		 * @param targetNode 目标节点
		 * @param pathMap 逻辑地图
		 * @param useClockWise 是否使用顺时针取点
		 * @return 如果存在路径则返回路径数组，反则返回null
		 * 
		 */		
		public function calculatePath(startNode:PathNode, targetNode:PathNode, pathMap:PathMap, useClockWise:Boolean=true):Array
		{
			this._clockWise = useClockWise;
			this._startNode = startNode;
			this._targetNode = targetNode;
			this._pathMap = pathMap;
			this._startNode.g = 0;
				
			var path:Array = calPath(startNode);
			
			reset();
			return path;
		}
		
		private function calPath(startNode:PathNode):Array
		{
			var x:int = startNode.x;
			var y:int = startNode.y;
			
			//起点被放进关闭列表
			moveToCloseList(startNode);
			
			//获取周围的点
			var nodes:Array = _pathMap.getAroundNodes(startNode, _clockWise);
			
			var p:PathNode;
			var path:Array;
			var g:int;
			var p2:PathNode;
			var len:int = nodes.length;
			
			//检测节点周围的点，按照条件放到开放或者关闭列表当中去
			for (var i:int=0; i<len; ++i)
			{
				p = nodes[i] as PathNode;
				
				if (p == _targetNode)
				{
					nodes = null;
					return [startNode, p];
				}
				
				if (!inList(p) && !p.isBarrier)
				{
					this._openList.push(p);
					this._openListFlag[p.key] = true;
					p.prevNode = startNode;
					p.targetNode = _targetNode;
					p.g = startNode.g + PathNode.DISTANCE;
					p.generateGHF();
				}
				else if (p.isBarrier)
				{
					moveToCloseList(p);
				}	
			}
			
			//检测开放列表
			if (this._openList.length > 0)
			{
				//sort is the king of speed
				this._openList.sortOn(["f", "h", "x", "y"], Array.NUMERIC);
				p2 = this._openList[0] as PathNode;
				
				if (p2 == _targetNode)
				{
					return [startNode, p2];
				}
				else
				{
					path = calPath(p2);
					
					if (!path.length)
					{
						return [];
					}
					else
					{
						var result:Array = [startNode];
						var len2:int = path.length;
						//去除多余的路径节点，相对于之前的版本进行了优化，理论上能够过滤出更短的路径
						for (g=0; g<len2; ++g)
						{
							p2 = path[g] as PathNode;
							var distance:int = Math.abs(p2.x - startNode.x) + Math.abs(p2.y - startNode.y);
							
							if (distance == 0)
							{
								result = [startNode];
							}
							else if (distance == 1)
							{
								result = [startNode, p2];
							}
							else
							{
								result.push(p2);
							}
						}
						
						return result;
					}
				}
			}
			
			return [];
		}
		
		private function moveToCloseList(pathNode:PathNode):void
		{
			var key:String = pathNode.key;
			this._openListFlag[key] = false;
			this._closeListFlag[key] = true;
			//this._closeList.push(pathNode);
			
			var len:int = this._openList.length;
			
			for (var i:int=0; i<len; ++i)
			{
				if (pathNode == _openList[i])
				{
					_openList.splice(i, 1);
					break;
				}
			}
		}
		
		private function inList(p:PathNode):Boolean
		{
			return (_openListFlag[p.key] || _closeListFlag[p.key]);
		}
	}
}